/*
    206. 反转链表
    给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
    输入：head = [1,2,3,4,5]
    输出：[5,4,3,2,1]
*/

// 迭代法
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  // 思路是从前往后遍历过程中，将节点放到头部位置
  if (!head) return null; // 特判
  let prev = null; // 上一次遍历之后的结果，也是最终生成的链表
  while (head) {
    // 保存当前的next引用，因为要将当前节点放到头部，需要改变当前节点next引用。
    // 如果直接修改，不保存，会改变当前遍历的cur，导致遍历出错
    let n = head.next;
    // 始终将当前节点放到生成链表的头部
    head.next = prev;
    // 将新生成的链表保存到prev变量上面
    prev = head;
    // 恢复当前遍历项cur的引用，防止遍历出错
    head = n;
  }
  return prev;
};

// 递归法
var reverseList = function (head) {
  if (!head || !head.next) return head; // 特判
  let p = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return p;
};
